package medium下个排序;

import org.testng.annotations.Test;

import java.util.Arrays;

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length == 1) {
            return;
        }
        int j=0;
        for (int i = nums.length-1; i > 0;i--) {
            if (nums[i]> nums[i-1]){
                j = i;
                break;
            }
        }
        if(j == 0){
            Arrays.sort(nums);
            return;
        }
//        Arrays.sort(nums,j,nums.length);

        for (int i = j;i < nums.length-1;i++){
            int tmp=i;
            for (int k = i+1;k < nums.length;k++){
                if (nums[k]<nums[tmp])
                    tmp=k;
            }
            int tmp1=nums[tmp];
            nums[tmp]=nums[i];
            nums[i]=tmp1;
        }
        for (int i = j; i < nums.length-1; i++) {
            int num = nums[i];
            int t = i;
            for (int k = i+1; k < nums.length; k++) {
                if (nums[t] > nums[k]){
                    t = k;
                }
            }
            nums[i]  = nums[t];
            nums[t]  = num;
        }

        for (int i = j; i < nums.length; i++) {
            if (nums[i] > nums[j-1]){
                int num = nums[j-1];
                nums[j-1] = nums[i];
                nums[i]  = num;
                break;
            }
        }

    }
    @Test
    public void test(){
        int[] nums = {5,4,7,5,3,2};
        nextPermutation(nums);
        for (int i:
                nums) {
            System.out.println(i);
        }
    }
}
